详细说明js实现线段相交的三种算法

这篇文章的内容很初级，主要针对像我这样的初学者，所以请拍拍算法帝王

引用

线段1(a，b)和线段2(c，d)是已知的，其中a b c d是终点，线段p的交点(平行或共线被认为是不相交的)

第一种算法：找到两条线的交点，然后判断交点是否在两条线上。

当我们求直线的交点时，可以用一般方程ax乘c=0来求(方程中的abc是一个系数，不是上面提到的终点，也可以用点斜方程和斜截面方程，这里暂时忽略)。

然后，根据交点与线段端点的位置关系，判断交点是否在线段上。

公式如下图：所示

Code class=' hljs avrasm '函数段intr (a，b，c，d) {/* * 1解线性方程组，求线段的交点。* *///如果分母为0，则为平行或共线，不相交的var分母=(b . y-a . y)*(d . x-c . x). if(分母==0){ return false；}//线段所在直线的交点坐标(x，y)var x=((b . x-a . x)*(d . x-c . x)*(c . y-a . y)(b . y-a . y)*(d . x-c . x)var y=-((b . y-a . y)*(d . y-c . y)*(c . x-a . x)(b . x-a . x)*(d . y-c . y)* a . y-(d . x-c)/** 2判断交点是否在两条线段上**/如果(///交点在线段1上(x-c . x)*(x-d . x)=0(y-c . y)*)*(y-b . y)=0//且交点也在线段2上(x-c.x. (y-d.y)=0 ){ //返回交点p return {x : x，y : y}} //否则，返回false无交点} /代码算法清晰容易因为在不确定交点是否有效(在线段上)之前，需要花费大量的时间来计算交点。

如果发现交点无效，就会浪费之前的计算，整个计算过程比较复杂。

那么，有没有办法在计算之前判断是否有有效的交点呢？

显然，答案是肯定的。所以有一些后来的算法。

算法2 :判断每条线段的两个端点是否在另一条线段的两侧，如果是，则找到两条线段所在直线的交点，否则不相交。

第一步是判断两点是否在某一线段的两侧，通常采用投影法：

得到线段的法向量，然后将点投影到法向量线上。最后根据投影位置判断点与线段的关系。

见下文

A点和B点在线段cd的法线上的投影如图所示。此时，我们需要在法线上投影线段cd(选择点C或点D)。

主要用于参考。

A点和B点投影在图中点C的两侧，表示线段ab的端点在线段cd的两侧。

同理，再次判断cd是否在线段ab两侧就足够了。

寻找法线和投影听起来很复杂，但实际上对我来说相当复杂。几个月前不知道(学习的时候忘了： '()')。

幸运的是，学习和实现并不复杂，有公式可循

求线段ab :的法线

var nx=b.y - a.y，ny=a . x-b . x；var normalLine={ x: nx，y : ny }；注意：其中normalLine.x和normalLine.y的几何意义代表法线方向而不是坐标。

求点C在法线：上的投影位置

var dist=NormalLine . x * c . x NormalLine . y * c . y；请注意，中的“投影位置”是一个标量，表示到法线原点的距离，而不是投影点的坐标。

知道这个距离通常就够了。

当我们求出A点(distA)的投影、B点(distB)的投影和C点(distC)的投影时，就可以很容易地根据它们的大小来判断相对位置。

当distA==distB==distC时，两条线段共线

distA==distB！=distC，两条线段平行

当distA和distB位于distC的同一侧时，两条线段不会相交。

当distA和distB位于distC的不同侧时，有必要

前面的步骤只实现了‘判断线段是否相交’。当结果为真时，需要进一步寻找交点。

后面我们会讲到寻找交点的过程，先来看看算法：的完整实现

函数段intr (a，b，c，d){//线段ab的法线n1varnx1=(b.y-a.y)，ny1=(a . x-b . x)；//线段cd n2varnx2的法线=(d.y-c.y)，ny2=(c . x-d . x)；//穿过两条法线。如果结果为0，则表示线段ab和线段cd平行或共线，不相交的var分母=nx1 * ny2-ny1 * nx2；if(分母==0){ return false；}//正常N2上的投影vardistc _ N2=nx2 * c . xny 2 * c . y；var distA _ N2=nx2 * a . x ny2 * a . y-distC _ N2；var distB _ N2=nx2 * b . x ny2 * b . y-distC _ N2；//点A的投影和点B的投影与点C的投影在同一侧(这种情况下，点被视为不相交)；if(distA _ N2 * distB _ N2=0){ return false；}/////判断c点、d点与线段ab的关系。原理同上。///vardista _ N1在法线n1=nx1 * a.xny1 * a.y上的投影；var distC _ N1=nx1 * c . x ny1 * c . y-distA _ N1；var distD _ N1=nx1 * d . x ny1 * d . y-distA _ N1；if(distC _ N1 * distD _ N1=0){ return false；}//计算交点坐标var fraction=dista _ N2/分母；var dx=分数* ny1，dy=-分数* nx1返回{ x: a.x dx，y : a . y dy }；}最后，用来找交点坐标的方法好像有点奇怪，有一种被迷惑的感觉。

其实和第一个算法中的算法差不多，只是很多计算项都是事先计算好的。

换句话说，在第二种算法中，求交点坐标的部分实际上是利用直线的线性方程来完成的。

现在让我们对算法一和算法二：做一个简单而不科学的比较

1.在最好的情况下，这两种算法的复杂性是相同的

2.在最坏的情况下，算法1和算法2的计算量是相似的

3.但是算法2提供了更多的“提前结束条件”，所以平均来说，算法2应该更好。

经过实际测试，实际情况也是如此。

前两种算法基本通用，可以应对大多数情况。但其实有一个更好的算法，是我最近才学会的(我现在已经学会了，卖了，所以不介意……)

算法3 :判断每条线段的两个端点是否在另一条线段的两侧，如果是，则找到两条线段所在直线的交点，否则不相交。

(咦？为什么感觉和算法二一样？不要怀疑它是完全一样的.)

所谓算法三其实只是算法二的改进，改进主要是：

点与线段的位置关系不是通过法线投影来判断的，而是通过点与线段形成的三角形面积来判断的。

首先，复习三角形面积公式：已知三角形有三个点a(x，y) b(x，y) c(x，y)，三角形面积为：

code class=' hljs avrasm ' var triArea=((a . x-c . x)*(b . y-c . y)-(a . y-c . y)*(b . x-c . x))/2；/code因为两个向量的交叉等于两个向量组成的平行四边形的面积(以两个向量为邻边)，上面的公式不难理解。

因为向量有方向，所以面积也有方向。通常我们以逆时针为正，顺时针为负。

改进算法的关键点是：

如果线段ab和点C形成的三角形面积的正负符号与线段ab和点D形成的三角形面积的正负符号不同，

那么点c和d位于线段ab的两侧。

:如下图所示

图中虚线所示的三角形缠绕方向不同(三边的定义顺序)，所以面积的正负符号不同。

让我们先看看代码：

由于我们只需要判断符号，所以不需要将三角形面积公式除以2。

函数段intr (a，b，c，d){//三角形面积的两倍ABC var area _ ABC=(a . x-c . x)*(b . y-c . y)-(a . y-c . y)*(b . x-c . x)；//三角形的abd面积的两倍var area _ Abd=(a . x-d . x)*(b . y-d . y)-(a . y-d . y)*(b . x-d . x)；//如果面积符号相同，则两点在线段的同一侧，不相交(这种情况下，线段上的点被视为不相交)；if(area _ ABC * area _ Abd=0){ return false；}//三角形面积的两倍CDA var area _ CDA=(c . x-a . x)*(d . y-a . y)-(c . y-a . y)*(d . x-a . x)；//三角形cdb面积的两倍//注意这里有一个小优化。不需要通过公式计算面积，而是通过加减三个已知面积。var area _ CDB=area _ CDA area _ ABC-area _ Abd；if(area _ CDA * area _ CDB=0){ return false；}//计算交点坐标var t=area _ CDA/(area _ Abd-area _ ABC)；var dx=t*(b.x - a.x)，dy=t *(b . y-a . y)；返回{ x: a.x dx，y : a . y dy }；}最后，交点坐标的计算与第二种算法相同。

算法3在算法2的基础上，大大简化了计算步骤，使代码更简单。可以说是三种算法中最好的，实际测试结果也是一样的。

当然，说实话，在Javascript中，三种算法的时间复杂度对于普通计算来说几乎是一样的(尤其是在V8引擎下)。在我的测试案例中，我还做了异常百万的亚等级线相交测试，来拉开三种算法的差距。

摘要

但本着精益求精的精神和学习的态度，追求更好的算法总是有积极意义的。这是几种利用js实现线段相交的算法。内容不是很深刻，希望对大家学习js有帮助。

版权声明：详细说明js实现线段相交的三种算法是由宝哥软件园云端程序自动收集整理而来。如果本文侵犯了你的权益，请联系本站底部QQ或者邮箱删除。